package com.it.data_recursion.fibonacci;

import java.util.Arrays;

/**
 * @Author: Coke
 * @DateTime: 2023/05/23/19:30
 * @注释: 斐波那契
 **/
public class Fibonacci {
    // 第 0 项 = 0
    // 第 1 项 = 1
    // 第 2 项 = 0 + 1 = 1
    // 第 n 项 = n-1项 + n-2项
    
    /**
     * @param n: 第 n 项
     * @return int 值
     * @作者: Coke
     * @注释: 求斐波那契数列 第 n 项的值
     * @DateTime: 2023/5/23 21:47
     */
    public static int fibonacci (int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        int x = fibonacci(n - 1);
        int y = fibonacci(n - 2);
        return x + y;
    }

    /**
     * @Author: CaoYouGen
     * @注释: 第 n 项的斐波那契值
     * @DateTime: 2023/5/24 13:04
     *
     * @param n: 斐波那契 的 第 n 项
     * @return int  斐波那契 的 第 n 项的值
     */
    public static int fibonacciPro(int n){
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        return toFibonacciPro(n, cache);
    }

    /**
     * @Author: CaoYouGen
     * @注释: 第 n 项的斐波那契值（执行逻辑）
     * @DateTime: 2023/5/24 13:04
     *
     * @param n: 斐波那契 的 第 n 项
     * @param cache:  缓存计算过的值
     * @return int 斐波那契 的 第 n 项的值
     */
    private static int toFibonacciPro(int n, int[] cache){
        if (cache[n] == -1){
            int x = toFibonacciPro(n - 1, cache);
            int y = toFibonacciPro(n - 2, cache);
            cache[n] = x + y;
        }
        return cache[n];
    }

}

